There are a number of known methods for digital data resolution conversion. For example, transform domain methods such as the fractional Fourier transform (fractional FFT or Chirp-Z transform), the discrete cosine transform (DCT), and discrete wavelet transform (DWT). In addition, there are a number of spatial domain methods such as re-sampling and digital filtering with finite-impulse response (FIR) and infinite-impulse response (IIR) filters and interpolation with continuous, usually cubic, splines. The spline interpolation technique is one interpolation method which can be efficiently implemented using convolution with a continuous kernel. When the continuous kernel produces data that passes through the original data points of an input signal, the kernel is often called an interpolating kernel and when the interpolated data produced is not constrained to pass through the original data points it is often called an approximating kernel.
Prior art continuous kernels for digital data resolution conversion include the nearest neighbour (NN), linear, quadratic, and cubic kernels. The NN kernel is the simplest method, which interpolates the image with the pixel value that is spatially nearest to the required one. The NN kernel works quite well when the scaling ratio is an integer multiple of the original data as it introduces no new values (ie., no new colours), and preserves sharp edges. However, at other ratios the NN kernel has the disadvantage of shifting edge locations which often produces visible distortions in the output image, especially in images containing text or fine line details. Linear interpolation on the other hand allows for the introduction of new grey levels (or colours) that are effectively used to position edges at sub-pixel locations. However, the Linear interpolation method has the disadvantage of making sharp edges which can appear to be blurred. Quadratic and cubic interpolation provide steeper step responses and therefore less edge blurring, however, the steeper response results in an overshoot on either side of the edge. These overshoots can make the edges in natural images appear sharper, but on text, fine lines, or other computer generated graphics these overshoots are clearly visible and detract from the perceived image quality and text legibility.
In view of the foregoing discussion, it can be concluded that each kernel has its own strengths and weaknesses, ie., there are certain image areas which are best interpolated using kernels of different shapes. Simply applying a single continuous convolution kernel at every image pixel will not satisfy all of the requirements for a general-purpose resolution conversion application.
The publication U.S. Pat. No. 5,131,057 discloses a kernel with both a steep step response, but no overshoot whereby the parameters of the cubic kernel are adjusted according to image information. U.S. Pat. No. 5,131,057 discloses a two-parameter Catmull-Rom cubic kernel of the form:                               h          ⁢                      (            s            )                          =                  {                                           ⁢                                                                                                                                        (                                                  2                          -                                                                                    3                              2                                                        ⁢                            b                                                    -                          c                                                )                                            ⁢                                                                                                  s                                                                          3                                                              +                                                                  (                                                                              -                            3                                                    +                                                      2                            ⁢                            b                                                    +                          c                                                )                                            ⁢                                                                                                  s                                                                          2                                                              +                                          (                                              1                        -                                                                              1                            3                                                    ⁢                          b                                                                    )                                                        ,                                                                                                                      s                                                        ≤                  1                                                                                                                                                (                                                                                                    -                                                          1                              6                                                                                ⁢                          b                                                -                        c                                            )                                        ⁢                                                                                          s                                                                    3                                                        +                                                            (                                              b                        +                                                  5                          ⁢                          c                                                                    )                                        ⁢                                                                                          s                                                                    2                                                        +                                                                              1                  <                                                          s                                                        ≤                  2                                                                                                                                                                        (                                                                                                            -                              2                                                        ⁢                            b                                                    -                                                      8                            ⁢                            c                                                                          )                                            ⁢                                                                      s                                                                                      +                                          (                                                                                                    4                            3                                                    ⁢                          b                                                +                                                  4                          ⁢                          c                                                                    )                                                        ,                                                                                                                                                                                     0                  ,                                                            Otherwise                                              ⁢                                                                     (        1        )            
Choosing parameters b and c (b=0, c=0.5), results in an interpolating cubic that agrees with the first three terms of the Taylor series expansion of the original image, and choosing (b=1, c=0) results in the approximating cubic B-spline. In U.S. Pat. No. 5,131,057 the parameter b is fixed at b=0, whilst c is varied between 0, 0.5, and 1 dependent upon the edge strength measured using a Laplacian of Gaussian (LOG) edge detector. At a sharp edge c=0 the resulting cubic is:                               h          ⁡                      (            s            )                          =                  {                                           ⁢                                                                                                                2                      ⁢                                                                                                  s                                                                          3                                                              -                                          3                      ⁢                                                                                                  s                                                                          2                                                              +                    1                                    ,                                                                                                                      s                                                        ≤                  1                                                                                                      0                  ,                                                                              Otherwise                  .                                                              ⁢                                                                     (        2        )            
There is however, a problem with using the kernel disclosed in U.S. Pat. No. 5,131,057 to interpolate image data when the re-sampled pixel displacement is not significantly different from the original pixel displacement, say a re-sampling ratio of 10/11 or 11/10. In that instance, pixels at the edges of text and other fine lines take on a grey value rather than the original black or white values resulting in the blurring of sharp edges and a reduction in the observed image quality.
A further problem with conventional continuous convolution kernels is associated with their application to edges at oblique orientations in an image plane. Conventional kernels can be either applied in a separable fashion, ie., first to the rows of the image and then to the columns, or applied in a 2-dimensional form where the kernels are directly convolved with the 2-dimensional image data. However, the kernel orientations in these implementations are limited to either: horizontal, vertical, or symmetrical. Upon encountering an oblique edge, the pixels on either side of an edge are primarily used in the interpolation rather than pixels along the edge resulting in an interpolated edge that no longer appears to be clean and smooth, but appears to be jagged, or blurred, or both. The publication U.S. Pat. No. 5,446,804, discloses a method which prevents interpolation across edges by using extrapolated estimates of pixel values for pixels on the other side of the edge in the bilinear interpolation. However, the method disclosed by U.S. Pat. No. 5,446,804 requires highly accurate sub-pixel edge estimation at the output resolution and iterative post-processing using a successive approximation procedure, which place high demands on memory and processing resources.
The publication U.S. Pat. No. 5,125,042 discloses a method for selecting interpolation kernels based on edge strength, or user input. However, there are some defects that prevent the method disclosed by U.S. Pat. No. 5,125,042 from working optimally. Firstly, the use of edge strength alone as the basis for kernel selection does not provide sufficient information for reliable kernel selection (especially at oblique edges). Secondly, Kernel selection based solely upon user input is impractical and does not specify the kernel selection in enough detail. For example, in the sub-image shown in FIG. 7 of U.S. Pat. No. 5,125,042, there is not one single kernel that is ideal for the whole sub-image. In general, different kernels are required at a resolution that is impractical to be specified by a user.
Kernel selection needs to be both automatic and reliable so that the appropriate kernel can be used on different edge strengths and edge directions that are typically found in images.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.